public class BinarySearchTree {
  static class TreeNode{
      public int val ;
      public TreeNode left ;
      public TreeNode right ;

      public TreeNode(int val) {
          this.val = val;
      }

  }
  public TreeNode root = null ;
  public boolean search(int val){
      TreeNode cur = root ;
      while (cur != null){

          if(val > cur.val){
              cur = cur.right ;
          }else   if(val < cur.val){
              cur = cur.left;
          }else {
              return true ;
          }
      }
      return false ;

  }
  public boolean insert(int val){
       TreeNode node = new TreeNode(val) ;
       if(root == null){
           this.root = node ;
           return true ;
       }
       TreeNode parent = null ;
       TreeNode cur = root ;
       while(cur != null){
           parent = cur ;
           if(val > cur.val){
               cur = cur.right ;
           }else if(val < cur.val){
               cur = cur.left ;
           }else {
               return false ;
           }
       }
           if(val > parent.val){
               parent.right = node ;
           }else {
               parent.left = node;
           }

       return true ;
  }

  public void remove(int val){
      TreeNode parent = null ;
      TreeNode cur = root ;
      while(cur != null){
          parent = cur ;
          if(val > cur.val){
              cur = cur.right ;
          }else if(val < cur.val){
              cur = cur.left ;
          }else {
               // 删除的逻辑
              removeNode(parent , cur);
          }
      }
      

  }

    private void removeNode(TreeNode parent, TreeNode cur) {
        //左子树为空
      if(cur.left == null && cur.right != null){
              //如果cur是root
               if(cur == root){
                   root = cur.right;
                   return;
               }
               if(cur == parent.left){
                   parent.left = cur.right;
               } else {
                   parent.right = cur.right;
               }
          //右子树为空
        } else if (cur.right == null && cur.left != null) {
          if(cur == root){
              root = cur.left;
              return;
          }
          if(cur == parent.left){
              parent.left = cur.left;
          } else  {
              parent.right = cur.left;
          }
          //两边都为空
        }else{
             //找左子树的最右节点
               TreeNode target = cur.left ;
               TreeNode tParent = cur ;
               while(target.right != null){
                   tParent = target ;
                   target = target.right;
               }
               //找到最右节点把他的值覆盖掉cur的值；
               cur.val = target.val ;
               if(cur.left == target){
                   cur.left = target.left;
               }else {
                   //让tParent的right指向 target的left；
                   tParent.right = target.left ;
               }

        }


    }

}
